package com.taldh.algorithm.listnode;

import org.junit.Test;

public class MyLinkedList {

    private int val;
    private MyLinkedList next;
    private MyLinkedList prev;
    private MyLinkedList header;

    /** Initialize your data structure here. */
    public MyLinkedList() {

    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        MyLinkedList cur = header;
        for(int i = 1; i < index + 1 ; i++) {
            if (cur == null) {
                return -1;
            } 
            if (i == index) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        if (header == null) {
            header = new MyLinkedList();
            header.val = val;
        } else {
            MyLinkedList temp = header;
            header = new MyLinkedList();
            header.val = val;
            header.next = temp;
            temp.prev = header;
        }
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if (header == null) {
            header = new MyLinkedList();
            header.val = val;
        } else {
            MyLinkedList cur = header;
            while (cur.next != null) {
                cur = cur.next;
            }
            MyLinkedList node = new MyLinkedList();
            node.val = val;
            node.prev = cur;
            cur.next = node;
        }
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        MyLinkedList cur = header;
        for(int i = 1; i < index + 1 ; i++) {
            if (cur == null) {
                return;
            }
            if (i == index) {
                MyLinkedList node = new MyLinkedList();
                node.val = val;
                node.next = cur;
                MyLinkedList parent = cur.prev;
                if (parent != null) {
                    node.prev = parent;
                    parent.next = node;
                }
                cur.prev = node;
                if (i == 1) {
                    header = node;
                }
                return;
            }
            cur = cur.next;
        }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        MyLinkedList cur = header;
        for(int i = 1; i < index + 1; i++) {
            if (cur == null) {
                return;
            }
            if (i == index) {
                MyLinkedList parent =  cur.prev;
                if (parent != null) {
                    parent.next = cur.next;
                } else {
                    header = cur.next;
                }
                MyLinkedList child = cur.next;
                if (child != null) {
                    child.prev = parent;
                }
                return;
            }
            cur = cur.next;
        }
    }

    @Test
    public void test() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
        System.out.println(linkedList.get(1));
        linkedList.deleteAtIndex(1);  //现在链表是1-> 3
        System.out.println(linkedList.get(1));
    }

    @Test
    public void test2() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.deleteAtIndex(0);  //现在链表是1-> 3
        System.out.println(linkedList.get(1));
    }

    //["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]
    //[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]
    @Test
    public void test3() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(7);
        linkedList.addAtHead(2);
        linkedList.addAtHead(1);
        linkedList.addAtIndex(3,0);
        linkedList.deleteAtIndex(2);
        linkedList.addAtHead(6);
        linkedList.addAtTail(4);
        System.out.println(linkedList.get(4));
        linkedList.addAtHead(4);
        linkedList.addAtIndex(5,0);
        linkedList.addAtHead(6);
    }

    //["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
    //[[],[1],[3],[1,2],[1],[1],[1]]
    @Test
    public void test4() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1,2);
        System.out.println(linkedList.get(1));
        linkedList.deleteAtIndex(1);
        System.out.println(linkedList.get(1));
    }
}

/*
*
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
*/
